1. Field of the Invention
The present invention relates to a figure layout compaction method and compaction device, and particularly to a figure layout compaction device and compaction method for such a device that performs compaction processing in component arrangement and wiring design for printed circuit boards and integrated circuits.
2. Description of the Related Art
Automatic layout devices are used in designing the layout of large-scale semiconductor integrated circuits and the layout of printed circuit boards, and various types of compaction techniques have been proposed for this type of layout device.
As a first example of the prior art, one known method is disclosed in "Design Modification Method for Semiconductor Integrated Circuits" of Japanese Patent Laid-open No. 165654/90. According to this method, when adding new wiring to an already existing layout, compaction separation lines and the region in their vicinity are specified and wiring already existing within this range is shifted to the periphery centering on compaction separation lines, thereby establishing a blank region having no wiring in the vicinity of compaction separation lines. New wiring may then be inserted in the blank region.
As a second example of the prior art, another known method is described in "LSI Layout Compaction Device" of Japanese Patent Laid-open No. 279373/89. The object of this invention is to efficiently discover modification portion which needs a modification process, reserve an area for the modification process, and to speedily execute the compaction process.
For this purpose, this LSI layout compaction device includes: a longest path search means for searching for the longest path made up of each figure element and wiring in a specified compaction direction for layout results representing the arrangement of figure elements representing each cell on an LSI chip and the wiring between each figure element; layout enlargement means for enlarging an blank region crossing this longest path in a direction opposite to the specified compaction direction; layout modification specification means for specifying that a portion of a figure element included in the longest path be shifted to this blank region; and compaction means for shifting a figure element specified by the layout modification specification means to an blank region and, after shifting, compacting the layout in the specified compaction direction.
As a third example of the prior art, another known method is disclosed in "Layout Compaction Device" of Japanese Patent Laid-open No. 151855/92. This device is provided with means for setting a compaction-prohibited area for block cells in every wiring layer, and means for compacting layout patterns based on the prohibited areas set by the prohibited area setting means.
In the compaction devices and compaction methods of the above-described prior art, wiring is compacted together through a compaction process by a means that compacts wiring, whereby wiring is arranged in a dense state with few gaps between wires. As a result, when new wiring is to be inserted, a compaction process must be executed to make a blank region for added wiring, as in the first prior-art method. Such methods have the drawback that a considerable amount of time is required by a compaction process for shifting the via-holes passing through multiple layers as well as the multiplicity of wiring in their vicinity.
As yet another method of the prior art, another known method is disclosed in "Compaction Method for Integrated Circuits" of Japanese Patent Laid-open No. 48750/92. This invention has the object of compacting the layout of each cell and wiring on an LSI chip into a smaller area. According to this invention, a component/wiring compaction means compacts the maximum limit of parts and horizontal/vertical wiring by arranging wires in horizontal and vertical directions into an arrangement area of the smallest dimensions, and then returns the position of via-holes that are connected to terminals as far as the positions of connecting terminals to form horizontal/vertical wiring.
In this prior-art compaction method, problems arise when diagonal lines exist in a pattern, as for example, when via-holes penetrating a plurality of layers are arranged in a row. In other words, in a case in which the first layer among a plurality of layers of patterns has a diagonal line that extends toward the upper right from below a via-hole on the left side to above a via-hole on the right side, the via-hole on the right side is judged to be below the via-hole on the left by way of the wiring; while conversely, if another layer has a diagonal line that extends toward the lower right from above the via-hole on the left side to below via-hole on the right side, the via-hole on the right side is judged to be above the via-hole on the left side by way of the wiring. Because this judgment contradicts the previous judgment, the vertical relationship of the left and right via-holes cannot be determined.
Furthermore, even in a single layer, in a case in which a polygon conductor shape having a concavity opening toward the right formed by a protruding side on the upper right and a protruding side on the lower right encloses a terminal within this concavity, this terminal is above the protrusion on the lower right of the polygonal conductor shape and at the same time below the protrusion on the upper right, resulting in the contradiction that the terminal is both above and below the polygonal conductor shape, whereby the vertical relationship between the polygonal conductor shape and the terminal cannot be determined.
In this way, compaction methods of the prior art have the drawback that the compaction process cannot be executed due to the inability to determine vertical relationships for patterns having diagonal wiring lines or polygonal conductor shapes.